//给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内 
// -10⁵ <= Node.val <= 10⁵ 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
//
// 
//
// 
// 注意：本题与主站 148 题相同：https://leetcode-cn.com/problems/sort-list/ 
//
// Related Topics 链表 双指针 分治 排序 归并排序 👍 152 👎 0


package LeetCode.editor.cn;


import java.util.List;

/**
 * @author ldltd
 * @date 2025-03-04 19:57:29
 * @description LCR 077.排序链表
 
 */
 
public class SevenWHec2 {
    public static void main(String[] args) {
    //测试代码
    SevenWHec2 fun = new SevenWHec2();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

  //Definition for singly-linked list.
  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
        //自顶向下
    public ListNode sortList1(ListNode head) {
        return sortList( head,null);
    }
    public ListNode sortList(ListNode n1,ListNode n2){
            if(n1==null) return n1;
            //n1 n2都会传过来，这样防止成环
            if(n1.next==n2){
                n1.next=null;
                return n1;
            }
            ListNode slow=n1,fast=n1;
            while (fast!=n2){
                slow=slow.next;
                fast=fast.next;
                if(fast!=n2){
                    fast=fast.next;
                }
            }
            ListNode mid=slow;
            ListNode list1=sortList(n1,mid);
            ListNode list2=sortList(mid,n2);
            ListNode sorted=merge(list1,list2);
            return sorted;
    }
    public ListNode merge(ListNode n1,ListNode n2){
        ListNode t=new ListNode(-1);
        ListNode p1=n1,p2=n2;
        ListNode res=t;
        while (p1!=null&&p2!=null){
            if(p1.val<=p2.val){
                res.next=p1;
                p1=p1.next;
            }else {
                res.next=p2;
                p2=p2.next;
            }
            res=res.next;

        }
        if (p1!=null) {
            res.next=p1;
        }else if(p2!=null){
            res.next=p2;
        }
        return t.next;
    }

    public ListNode sortList(ListNode head){
        if(head==null) return head;
        int len=0;
        ListNode p=head;
        //计算长度
        while (p!=null){
            p=p.next;
            len++;
        }
        //哑结点
        ListNode res = new ListNode(-1, head);
        //长度从1 开始，每次加倍
        for (int i = 1	; i < len; i<<=1) {
            ListNode pre=res,curr=res.next;
            //分割区间
            while(curr!=null){
                ListNode head1=curr;
                //找到第一个区间最后一个元素
                for (int j = 1; j < i&&curr.next!=null; j++) {
                    curr=curr.next;
                }
                //保存这个区间下一个元素
                ListNode head2=curr.next;
                //将第一个区间的末尾置空，方便做终点
                curr.next=null;
                //计算第二个区间
                curr=head2;
                for (int j = 1; j < i&&curr!=null&&curr.next!=null; j++) {
                    curr=curr.next;
                }
                ListNode next=null;
                //如果没有遍历完，则保存第二个区间末尾的下一个元素，并将末尾置空，方便作为终点
                if(curr!=null){
                    next=curr.next;
                    curr.next=null;
                }
                //将前两个区间先合并
                ListNode merged=merge(head1,head2);
                pre.next=merged;
                //将pre放到两个区间的末尾的前一个不为空的位置
                while (pre.next!=null){
                    pre=pre.next;
                }
                //继续拆分
                curr=next;
            }
        }
        return res.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
